This invention relates to information storage and retrieval or transmission systems, and more particularly to means for encoding and decoding codewords for use in error detection, identification and correction in such information systems.
Digital information storage devices, such as magnetic disk, magnetic tape or optical disk, store information in the form of binary bits. Also, information transmitted between two digital devices, such as computers, is transmitted in the form of binary bits. During transfer of data between devices, or during transfer between the storage media and the control portions of a device, errors are sometimes introduced so that the information received is a corrupted version of the information sent. Errors can also be introduced by defects in a magnetic or optical storage medium. These errors must almost always be corrected if the storage or transmission device is to be useful.
Correction of the received information is accomplished by (1) deriving additional bits, called redundancy, by processing the original information mathematically; (2) appending the redundancy to the original information during the storage or transmission process; and (3) processing the received information and redundancy mathematically to detect, identify and correct erroneous bits at the time the information is retrieved. The process of deriving the redundancy is called encoding. The process of processing the received information and redundancy is called decoding. One class of codes often used in these processes is Reed-Solomon codes.
Encoding of information is accomplished by processing a sequence of information bits, called an information polynomial or information word, to devise a sequence of redundancy bits, called a redundancy polynomial or word, in accord with an encoding rule such as Reed-Solomon codes. An encoder processes the information polynomial with the encoding rule to create the redundancy polynomial and then appends it to the information polynomial to form a codeword polynomial which is transmitted over the signal channel or stored in an information storage device. When a codeword polynomial is received from the signal channel or read from the storage device, a decoder processes the received codeword polynomial to detect the presence of error(s), to attempt to identify any error(s) present and to flag the information polynomial as erroneous or to correct it before transferring the information polynomial for further processing.
The decoding process typically comprises three steps: (1) computing frequency-domain syndromes from the received codeword; (2) computing an error locator polynomial, whose roots indicate the locations of erroneous symbols, from the frequency-domain syndromes; and (3) finding the roots of the error locator polynomial and computing the corresponding error values.